package interview.dfs;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * 题目简述：树中每个节点有个权值，初始都为白色，从根节点开始每次操作两个相邻节点，
 * 若这两个节点权值成绩为完全平方数且都为白色，则可以将这两个节点同时染红，问最多可以染红多少个节点
 */
public class DoublePaintRedTree {

    static int WHITE=0, RED=1;
    static int[] w;
    static List<List<Integer>> list;

    /**
     * dfs函数定义：root为curRed颜色时root树的最大染红节点数sum
     * 先根据题目要求的 以及思路来确定函数定义，定义出一个求解模型
     */
    public static int dfs(int root, int fa, int color) {
        int sum = 0;
        if (color == WHITE) {
            //一、若root节点为白色，则先扫描记录不染的情况
            List<Integer> cands = new ArrayList<>();
            int white_sum = 0;
            for (Integer i : list.get(root)) {
                if (i == fa) continue;
                white_sum += dfs(i, root, WHITE);
                if (isNum(w[root], w[i])) {
                    cands.add(i);
                }
            }
            sum = white_sum;//全部不染的情况
            //然后再比较选一对染的最大价值
            for (Integer cand : cands) {
                //染root-cand对的价值为white_sum - 白色cand子树价值 + 红色cand子树价值 + root为红即1
                int tmp = white_sum - dfs(cand, root, WHITE) + dfs(cand, root, RED) + 1;
                sum = Math.max(sum, tmp);
            }
        } else {
            //二、若root节点为红色，则直接递归所有子节点
            for (Integer i : list.get(root)) {
                if (i != fa)
                    sum += dfs(i, root, WHITE);
            }
        }
        return sum;
    }

    public static boolean isNum(int t1, int t2) {
        return Math.sqrt(t1 * t2) - (int)Math.sqrt(t1 * t2) == 0;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        w = new int[n+1];
        list = new ArrayList<>();
        list.add(new ArrayList<>());
        for (int i = 1;i <= n;i++) {
            w[i] = sc.nextInt();
            list.add(new ArrayList<>());
        }
        for (int i = 1;i <= n-1;i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            list.get(u).add(v);
            list.get(v).add(u);
        }

        System.out.println(dfs(1, 0, WHITE));
    }
}
